//
// Created by 紫霄 on 2020/4/20.
//

#ifndef LEETCODE_40_H
#define LEETCODE_40_H
/*
 * 最小的k个数；
 *输入整数数组 arr ，找出其中最小的 k
个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
#include <vector>
using namespace std;
class Solution {
public:
  vector<int> getLeastNumbers(vector<int> &arr, int k) {
    //    vector<int> ans;
    //    if (k) {
    //      sort(arr.begin(), arr.end());
    //      for (int i = 0; i < k; ++i) {
    //        ans.push_back(arr[i]);
    //      }
    //    }
    //    return ans;   // 没啥意思
    vector<int> ans;
    if (k) {
      int sz = arr.size();
      if (sz == 1) {
        ans.push_back(arr[0]);
        return ans;
      }
      for (int i = 0; i < k; ++i) {
        for (int j = sz - 1; i < j; --j) {
          if (arr[j] < arr[j - 1]) {
            swap(arr[j], arr[j - 1]);
          }
        }
        ans.push_back(arr[i]);
      }
    }
    return ans;
  }
};
#endif // LEETCODE_40_H
